package CommonAlgs.sort;

import java.util.Arrays;

/**
 * 时间复杂度O(m+n)
 * 当给定输入种最大值很大的时候，这种排序算法就很浪费空间了
 * 缺点：浪费空间
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] input = {5, 3, 5, 2, 8};
        solution(input);
    }

    private static void solution(int[] input) {
        int size = max(input);
        int[] sortArr = new int[size + 1];
        for (int i : input) {
            sortArr[i]++;
        }
        for (int i = sortArr.length - 1; i > 0; i--) {
            for (int j = 0; j < sortArr[i]; j++) {
                System.out.print(i + "\t");
            }
        }
    }

    private static int max(int[] input) {
        int max_num = -99999;
        for (int i : input) {
            max_num = Math.max(max_num, i);
        }
        return max_num;
    }

}
